An important issue in the design of multiprocessor parallel processing networks is the connectivity between the processing nodes of the network. The type of connectivity directly affects such important system factors as the number of wires that must be attached to each processing node and the number of nodes a message must traverse to arrive at an intended destination node.
U.S. Pat. No. 4,247,892, issued to P. N. Lawrence, summarizes the approaches that have been used to solve the interconnection problem. In one method, a computer calls another and a link is established between the computers, similar to the way a telephone system functions. In a central clearinghouse method, a computer deposits a message in a central memory where it is picked up by a master computer and redeposited in an area accessible to all of the computers of a network. In a third method, messages are transmitted via intermediate processing nodes toward a destination node.
With respect to the third method, the Lawrence patent discloses two particularly beneficial network connectivity structures, the hierarchical tree structured network and the plateau distributed logarithmic structured network. In the tree network, the wiring between processing nodes is reduced because each node is connected only to a parent node and its child nodes, typically one or two. At the same time, the maximum number of nodes through which a message must pass en route to a destination node increases only linearly with the number of levels of the tree. Because of this, the tree structure is a particularly beneifical structure for parallel processing networks. A problem with the present state of the art of tree networks, however, is that the tree structure must be physically wired and, once done so, the structure is limited to working on only one problem at a time using the one tree.